﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class Survivor3
    {
        public Survivor3()
        {
            int testCount = Int32.Parse(Console.ReadLine());
            
            for (int testCase = 1; testCase <= testCount; testCase++)
            {
                int foodCount = Int32.Parse(Console.ReadLine());
                List<Food> foodList = new List<Food>();
                for (int i = 1; i <= foodCount; i++)
                {
                    string[] input = Console.ReadLine().Split(' ');
                    int start = Int32.Parse(input[0]);
                    int delay = Int32.Parse(input[1]);
                    foodList.Add(new Food(i, start, delay));
                }
                foodList = foodList.OrderBy(f => f.End).ToList();
                int[] eatTime = new int[foodList.Last().End + 1];
                eatTime[0] = -1; //-1은 음식을 먹어야 할 타이밍
                int maxTime = 0;
                for (int i = 0; i < foodList.Count; i++)
                {
                    Food now = foodList[i];
                    for (int j = now.Start; j >= 0; j--)
                    {
                        if (eatTime[j] == -1)
                        {
                            eatTime[j + now.Delay] = -1;
                            if (j + now.Delay > maxTime)
                            {
                                maxTime = j + now.Delay;
                            }
                        }
                    }
                }


                Console.WriteLine("Case #" + testCase + ": " + maxTime);
            }
        }
        class Food
        {
            public int Id { get; set; }
            public int Start { get; set; }
            public int Delay { get; set; }
            public int End { get; set; }
            public Food(int id, int start, int delay)
            {
                Start = start;
                Delay = delay;
                End = start + delay;
            }
            public override string ToString()
            {
                return Id + " : " + Start + " " + Delay + " " + End;
            }
        }
    }
}
